package com.gitee.ywj1352.算法.week02;

import java.util.*;

public class N皇后 {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> solutions = new ArrayList<List<String>>();
        int[] queens = new int[n];
        Arrays.fill(queens, -1);
        Set<Integer> columns = new HashSet<Integer>();
        Set<Integer> pie = new HashSet<Integer>();
        Set<Integer> na = new HashSet<Integer>();
        help(solutions, queens, n, 0, columns, pie, na);
        return solutions;
    }


    public void help(List<List<String>> solu, int[] queues, int n, int row, Set<Integer> colSet, Set<Integer> pieSet, Set<Integer> naSet) {
        if (row == n) {
            List<String> strings = generateBoard(queues, n);
            solu.add(strings);
        }
        for (int i = 0; i < n; i++) {
            int col = i;
            //联想下 对角线问题
            int pie = row + i;
            int na = i - row;
            if (colSet.contains(col) || pieSet.contains(pie) || naSet.contains(na)) continue;
            colSet.add(col);
            pieSet.add(pie);
            naSet.add(na);
            queues[row] = i;
            help(solu, queues, n, row + 1, colSet, pieSet, naSet);
            colSet.remove(col);
            pieSet.remove(pie);
            naSet.remove(na);
        }
    }


    public List<String> generateBoard(int[] queens, int n) {
        List<String> board = new ArrayList<String>();
        for (int i = 0; i < n; i++) {
            char[] row = new char[n];
            Arrays.fill(row, '.');
            row[queens[i]] = 'Q';
            board.add(new String(row));
        }
        return board;
    }

    public static void main(String[] args) {
        N皇后 n皇后 = new N皇后();
        List<List<String>> lists = n皇后.solveNQueens(12);
        for (List<String> ls : lists) {
            for (String s : ls) {
                System.out.println(s);
            }
            System.out.println();
        }
    }

}
